/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/05/28 15:32
 */
public class LinkedList {
    static class Node {
        Node pre;
        Node next;
        int value;
    }

    static Node sort(Node p) {
        Node head = new Node();//初始化一个空引用，指向头节点
        if (p != null) {
            head.next = p;
            p.pre = head;
        }
        while (p != null) {
            //从前往后找到插入点
            Node deep = head.next;
            while (deep.next != null && deep.value < p.value) {
                deep = deep.next;
            }
            //防止把p的后一位给弄丢，保存p的下一位
            Node next = p.next;
            //比最后一个大，就甩到最后
            if (deep.value < p.value) {
                deep.next = p;
                p.pre = deep;
            } else {//插入p
                p.next = deep;
                deep.pre.next = p;
                p.pre = deep.pre;
                deep.pre = p;
            }
            p = next;
        }
        return head.next;//head的下一个结点才是头节点，看第一行
    }
}
